//给定一个不含重复元素的整数数组 nums 。一个以此数组直接递归构建的 最大二叉树 定义如下： 
//
// 
// 二叉树的根是数组 nums 中的最大元素。 
// 左子树是通过数组中 最大值左边部分 递归构造出的最大二叉树。 
// 右子树是通过数组中 最大值右边部分 递归构造出的最大二叉树。 
// 
//
// 返回有给定数组 nums 构建的 最大二叉树 。 
//
// 
//
// 示例 1： 
//
// 
//输入：nums = [3,2,1,6,0,5]
//输出：[6,3,5,null,2,0,null,null,1]
//解释：递归调用如下所示：
//- [3,2,1,6,0,5] 中的最大值是 6 ，左边部分是 [3,2,1] ，右边部分是 [0,5] 。
//    - [3,2,1] 中的最大值是 3 ，左边部分是 [] ，右边部分是 [2,1] 。
//        - 空数组，无子节点。
//        - [2,1] 中的最大值是 2 ，左边部分是 [] ，右边部分是 [1] 。
//            - 空数组，无子节点。
//            - 只有一个元素，所以子节点是一个值为 1 的节点。
//    - [0,5] 中的最大值是 5 ，左边部分是 [0] ，右边部分是 [] 。
//        - 只有一个元素，所以子节点是一个值为 0 的节点。
//        - 空数组，无子节点。
// 
//
// 示例 2： 
//
// 
//输入：nums = [3,2,1]
//输出：[3,null,2,null,1]
// 
//
// 
//
// 提示： 
//
// 
// 1 <= nums.length <= 1000 
// 0 <= nums[i] <= 1000 
// nums 中的所有整数 互不相同 
// 
// Related Topics 栈 树 数组 分治 二叉树 单调栈 👍 338 👎 0

package leetcode.editor.cn;

import common.bean.TreeNode;
import common.util.MyUtil;

/**
 * Java：最大二叉树
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P654_MaximumBinaryTree {
    public static void main(String[] args) {
        Solution solution = new P654_MaximumBinaryTree().new Solution();
        int[] nums = MyUtil.createArray(3, 2, 1, 6, 0, 5);
        TreeNode treeNode = solution.constructMaximumBinaryTree(nums);
        MyUtil.printTreeNode(treeNode);
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public TreeNode constructMaximumBinaryTree(int[] nums) {
            if (nums == null || nums.length == 0) {
                return null;
            }
            int N = nums.length;
            // 生成最大值索引数组，TODO 可用单调栈
            int[][] max = new int[N][N];
            for (int i = 0; i < N; i++) {
                int maxIndex = i;
                for (int j = i; j < N; j++) {
                    maxIndex = nums[j] > nums[maxIndex] ? j : maxIndex;
                    max[i][j] = maxIndex;
                }
            }
            return process(max, nums, 0, N - 1);
        }

        private TreeNode process(int[][] max, int[] nums, int left, int right) {
            if (left < 0 || right >= nums.length || left > right) {
                return null;
            }
            int maxIndex = max[left][right];
            TreeNode node = new TreeNode(nums[maxIndex]);
            node.left = process(max, nums, left, maxIndex - 1);
            node.right = process(max, nums, maxIndex + 1, right);
            return node;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)

}